package october;

public class LongestCommonSubsequence {
    public static void main(String[] args) {
        String s1 = "adbc";
        String s2 = "habc";
        System.out.println(getLongestCommonSubsequence(s1, s2));

    }

    private static String getLongestCommonSubsequence(String s1, String s2) {
        if (s1 == null || s2 == null) return null;
        int l1 = s1.length(), l2 = s2.length();
        int[][] d = new int[l1 + 1][l2 + 1];

        for (int i = l1 - 1; i >= 0; i--) {
            for (int j = l2 - 1; j >= 0; j--) {
                if (s1.charAt(i) == s2.charAt(j)) {
                    d[i][j] = d[i + 1][j + 1] + 1;
                } else {
                    d[i][j] = Math.max(d[i + 1][j], d[i][j + 1]);
                }
            }
        }

        // recover LCS itself and print it to standard output
        StringBuilder sb = new StringBuilder();
        int i = 0, j = 0;
        while (i < l1 && j < l2) {
            if (s1.charAt(i) == s2.charAt(j)) {
                sb.append(s1.charAt(i));
                i++;
                j++;
            } else if (d[i + 1][j] >= d[i][j + 1]) i++;
            else j++;
        }
        return sb.toString();
    }
}
